package com.cqs.leetcode.tree;

import com.cqs.leetcode.TreeNode;

import java.util.Stack;

/**
 * @author lixqw
 * @date 2020/8/20
 */
public class RangeSumofBST938 {

   class Solution1{
       /**
        * 中根遍历 求[L,R]之间节点的和
        * 循环版
        * @param root
        * @param L
        * @param R
        * @return
        */
       public int rangeSumBST(TreeNode root, int L, int R) {
           Stack<TreeNode> stack = new Stack<>();
           if (root == null) return 0;
           int sum = 0;
           TreeNode node = root;
           while (!stack.isEmpty() || node != null) {
               while (node != null) {
                   stack.push(node);
                   node = node.left;
               }
               node = stack.pop();
               if (node.val >= L && node.val <= R) {
                   sum += node.val;
               }
               //结束遍历
               if (node.val > R) {
                   return sum;
               }
               node = node.right;
           }
           return sum;
       }
   }


   class Solution{
       int sum = 0;
       public int rangeSumBST(TreeNode root, int L, int R) {
           //递归终止条件
           if (root == null ) {
               return sum;
           }
           //注意，题目说了元素不重复 减枝
           if (root.val > L) {
               rangeSumBST(root.left, L, R);
           }
           if ( root.val >= L && root.val <=R) sum += root.val;
           //减枝
           if (root.val < R) {
               rangeSumBST(root.right, L, R);
           }
           return sum;
       }
   }

}
